package q2139_minMoves;

public class Solution_1 {
    /*
    得到目标值的最少行动次数
    贪心：
    应该反过来考虑该游戏
    * 目标是将给定的整数 target 变为 1；
    * 可以进行递减操作，将当前整数的值减 1；
    * 可以进行折半操作，将当前整数的值除以 2，前提是当前整数为偶数。
    由于我们的目标是将整数变为 1，因此在当前整数为偶数时，我们应当贪心地执行折半操作。
    优化
    在最坏的情况下，如果初始的折半操作次数为 0，
    那么我们会执行 target−1 次递减操作，时间复杂度为 O(target)，会超出时间限制。
    所以max = 0时就直接返回
     */
    public int minMoves(int target, int maxDoubles) {
        int ans = 0;
        while (maxDoubles != 0 && target != 1) {
            ++ans;
            if (target % 2 == 1) {
                --target;
            } else {
                --maxDoubles;
                target /= 2;
            }
        }
        ans += (target - 1);
        return ans;
    }
}
